package formal.tree.bst;

import java.util.Stack;

/**
 * @author DengYuan2
 * @create 2021-01-22 21:58
 */
public class M_538 {
    public static void main(String[] args) {
        Integer[] a ={4,1,6,0,2,5,7,null,null,null,3,null,null,null,8};
        TreeNode treeNode = TreeNode.generateTree(a);
        TreeNode res = convertBST(treeNode);
        System.out.println(res);
    }

    /**
     * 我的思路-迭代：按照中序遍历的样子，右-中-左，后面节点的值加上前面总的值即可
     * @param root
     * @return
     */
    public static TreeNode convertBST(TreeNode root) {
        if (root==null){
            return null;
        }
        int sum =0;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur =root;
        while (!stack.isEmpty() || cur!=null){
            while (cur!=null){
                stack.push(cur);
                cur=cur.right;
            }
            TreeNode node = stack.pop();
            sum+=node.val;
            node.val=sum;
            cur=node.left;
        }
        return root;
    }

    /**
     * 大神-中序遍历的递归形式
     */
    public static int sum =0;
    public static TreeNode convertBST2(TreeNode root){
        convertHelper(root);
        return root;
    }
    public static void convertHelper(TreeNode root){
        if (root==null){
            return;
        }
        convertHelper(root.right);
        sum+=root.val;
        root.val=sum;
        convertHelper(root.left);
    }
}
